package q691_minStickers;

import java.util.*;

public class Solution {
    /*
    从target出发【起始状态】，使用每个贴纸去掉对应个数的字母【状态转移】，看最终能否出现空字符串【目标状态】。
     */
    public int C(String[] stickers, String target) {
        Set<Character> targetSet = new HashSet<>();
        for(int i = 0; i < target.length(); i++){
            // 先将所有target字符放入set中
            targetSet.add(target.charAt(i));
        }
        List<Map<Character, Integer>> availables = new ArrayList<>();
        for(String s: stickers) {
            // 对于每一个贴纸 我们使用getCount方法
            // 该方法会统计该贴纸中每个字符的数量 例如对于abb ——> {'a':1, 'b':2}
            Map<Character, Integer> map = getCounter(s, targetSet);
            if(map != null) {
                availables.add(map);
            }
        }
        // 建立一个队列 使用BFS的方法
        Deque<String> queue = new ArrayDeque<>();
        queue.addLast(target);
        // cost代表我们还没有完成的拼贴字符 以及当前所用的贴纸数量
        Map<String, Integer> cost = new HashMap<>();
        cost.put(target, 0);
        while(!queue.isEmpty()) {
            String cur = queue.pollFirst();
            // 从之前所录入的贴纸中寻找
            for(Map<Character, Integer> map: availables) {
                // 如果当前遍历到的map中有cur中首个字符的Key
                // 因为我们优先从左往右去掉当前状态中的字符，减少排列组合情况
                // 所以只要从左向右找到了有该字符的map 就开始删除

                // 并且同样的字符可能出现在多个map（贴纸）中 所以使用bfs
                // 意味着在一次遍历后 会出现多种不同的nxt
                if(map.containsKey(cur.charAt(0))) {
                    // nxt代表这次剪切后还有哪些字符需要拼
                    String nxt = nextState(cur, new HashMap<>(map));
                    if(nxt.length() == 0) {
                        // 这种方法显然是最先剪贴完毕的所需要的贴纸最少
                        return cost.get(cur) + 1;
                    } else if(!cost.containsKey(nxt)) {
                        // 当nxt不在cost中时 将nxt放入并加入到队列 进入下一次层序遍历
                        cost.put(nxt, cost.get(cur) + 1);
                        queue.addLast(nxt);
                    }
                }
            }
        }
        return -1;
    }

    private Map<Character, Integer> getCounter(String s, Set<Character> chars) {
        Map<Character, Integer> map = new HashMap<>();
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(chars.contains(c)) {
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
        }
        return map.size() > 0 ? map : null;
    }

    private String nextState(String s, Map<Character, Integer> map) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 对应map中的数量要减少
            if(map.getOrDefault(c, 0) > 0) {
                map.put(c, map.get(c) - 1);
            } else {
                // 如果是map中没有的字符 则加入sb
                sb.append(c);
            }
        }
        // 最后返回这次剪切后剩下没有拼出来的字符
        return sb.toString();
    }
}
